<?php if (!defined('CORE_DIR')) die('Wrong entry point!');

/* 
 * Copyright 2010 Anton Muraviev a.k.a kuromaisu
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 */

Aero::define('AeroDiff', AS_CLASS);

define('DIFF_MODE_LINE', 0);
define('DIFF_MODE_WORD', 1);
define('DIFF_MODE_CHAR', 2);

define('DIFF_OP_DELETE',0);
define('DIFF_OP_ADD',1);
define('DIFF_OP_MODIFY',2);
define('DIFF_OP_COPY',3);

class AeroDiff
/*
 * A simple diff library.
 */
{
	public function diff($a, $b, $mode = DIFF_MODE_LINE, $sync = true)
	{
		if ($mode === DIFF_MODE_LINE)
		{
			// Normalize, break into lines and clear empty elements
			$a = str_replace("\r\n","\n",$a);
			$a = str_replace("\r","\n",$a);
			$a_l = explode("\n",$a);
		
			$b = str_replace("\r\n","\n",$b);
			$b = str_replace("\r","\n",$b);
			$b_l = explode("\n",$b);
		}
		else
		{
			$pattern = '~&\#?[a-z0-9]+;|</?[a-z]+[^>]*>|\w+|\W~iu';

			preg_match_all($pattern, $a, $backrefs);
			$a_l = array_filter(array_shift($backrefs));

			preg_match_all($pattern, $b, $backrefs);
			$b_l = array_filter(array_shift($backrefs));
		}
		
		$a_c = count($a_l);
		$b_c = count($b_l);
		
		// Start comparing
		$a_i = $b_i = 0;
		$a_r = $b_r = array();
		
		while ($a_i < $a_c && $b_i < $b_c)
		{
			// If two strings are equal, save them as copy and continue
			if ($b_l[$b_i] === $a_l[$a_i])
			{
				$a_r[] = array(DIFF_OP_COPY, $a_l[$a_i]); $a_i++;
				$b_r[] = array(DIFF_OP_COPY, $b_l[$b_i]); $b_i++;
				continue;
			}
			
			// Search both arrays for the first match
			$_a_i = $a_i;
			$_b_i = $b_i;
			
			while ($_a_i < $a_c || $_b_i < $b_c)
			{
				$__a_i = $a_i;
				$__b_i = $b_i;
				
				if ($_a_i === $a_c) $_a_i--;
				if ($_b_i === $b_c) $_b_i--;
				
				do {
					if ($a_l[$_a_i] === $b_l[$__b_i])
					{
						$_b_i = $__b_i;
						break 2;
					}
					
					$__b_i++;
				} while ($__b_i <= $_b_i);
				
				do {
					if ($b_l[$_b_i] === $a_l[$__a_i])
					{
						$_a_i = $__a_i;
						break 2;
					}
					
					$__a_i++;
				} while ($__a_i <= $_a_i);
				
				if ($_a_i < $a_c) $_a_i++;
				if ($_b_i < $b_c) $_b_i++;
			}
			
			// Search for modifications
			if ($mode === DIFF_MODE_LINE)
			{
				while ($_a_i > $a_i || $_b_i > $b_i)
				{
					if ($_a_i > $a_i && $_b_i > $b_i)
					{
						list($_a_r, $_b_r) = $this->diff($a_l[$a_i],$b_l[$b_i], DIFF_MODE_WORD, false);
						
						if ($this->entropy($_a_r) > 0.2 && $this->entropy($_b_r) > 0.2)
						{
							$a_r[] = array(DIFF_OP_MODIFY, $a_l[$a_i], $_a_r);
							$b_r[] = array(DIFF_OP_MODIFY, $b_l[$b_i], $_b_r);
							$a_i++;$b_i++;
							continue;
						}
					}
					
					if ($_a_i > $a_i)
					{ 
						$a_r[] = array(DIFF_OP_DELETE, $a_l[$a_i]);
						$a_i++;
					}
					else if ($sync)
					{
						$a_r[] = array(DIFF_OP_ADD, '&nbsp;');
					}
					
					if ($_b_i > $b_i)
					{ 
						$b_r[] = array(DIFF_OP_ADD, $b_l[$b_i]); 
						$b_i++;
					}
					else if ($sync)
					{
						$b_r[] = array(DIFF_OP_DELETE, '&nbsp;'); 
					}
				}
			}
			else
			{
				while ($_a_i > $a_i) { $a_r[] = array(DIFF_OP_DELETE, $a_l[$a_i]); $a_i++; }
				while ($_b_i > $b_i) { $b_r[] = array(DIFF_OP_ADD, $b_l[$b_i]); $b_i++; }
			}
		}
		
		
		return array($a_r,$b_r);
	}
	
	public function entropy($changeset)
	{
		if (count($changeset) === 0)
		{
			return 0;
		}
		
		$max_copied = 0;
		$copied = 0;
		
		foreach ($changeset as $change)
		{
			if ($change[0] === DIFF_OP_COPY)
			{
				$copied++;
			}
			else
			{
				$max_copied = max($max_copied, $copied);
				$copied = 0;
			}
		}
		
		return $max_copied / count($changeset);
	}
	
	public function display($changeset, $word = false)
	{
		$output = '';
		
		foreach ($changeset as $change)
		{
			if (!$word) switch($change[0])
			{
				case DIFF_OP_COPY:
					$output.= '<li>'.$change[1]."</li>\n"; break;
				case DIFF_OP_ADD:
					$output.= '<li class="ins">'.$change[1]."</li>\n"; break;
				case DIFF_OP_DELETE:
					$output.= '<li class="del">'.$change[1]."</li>\n"; break;
				case DIFF_OP_MODIFY:
					$output.= '<li class="mod">'.$this->display($change[2],true)."</li>\n"; break;
			} else switch($change[0]) {
				case DIFF_OP_COPY:
					$output.= $change[1]; break;
				case DIFF_OP_ADD:
					$output.= '<ins>'.$change[1].'</ins>'; break;
				case DIFF_OP_DELETE:
					$output.= '<del>'.$change[1].'</del>'; break;
			}
		}
		
		if (!$word)
		{
			return '<ul>'.$output.'</ul>';
		}
		
		return $output;
	}
}
